/**    
 * 文件名：Apriori.java    
 *    
 * 版本信息：    
 * 日期：2016年11月12日    
 * Copyright ISITEAM Corporation 2016     
 * 版权所有    
 *    
 */


import java.io.BufferedReader;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileReader;
import java.io.FileWriter;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.Map;
import java.util.HashSet;
import java.util.Iterator;
import java.util.List;
import java.util.Set;
import java.util.TreeMap;
/**    
 *     
 * 项目名称：DataMing_Apriori    
 * 类名称：Apriori    
 * 类描述：    
 * 创建人：OliverQiao    
 * 创建时间：2016年11月12日 下午10:03:27    
 * 修改人：OliverQiao    
 * 修改时间：2016年11月12日 下午10:03:27    
 * 修改备注：    
 * @version     
 *     
 */
public class Apriori {	
	
	public static void main(String[] args) throws FileNotFoundException {
		// TODO Auto-generated method stub
		float support_per=0.01f;
		
		ArrayList<String> tlist=getTransactionFromFile("categories.txt");
		int support=(int) (support_per*tlist.size());
		
		System.out.println(tlist.size());
		System.out.println("频繁1项集:");
		Map<String,Integer> L1=find_frequent_1_itemsets(tlist,0.01f);
	//	L1=sortMapByKey(L1);
      String test="test";
      
	 Map<String,Integer> Lk_1=L1;
	 Map<String,Integer> L=new TreeMap<String,Integer>(); 
	 int round=1;
	 while(Lk_1.size()!=0){
		 round++;
		 System.out.println("挖掘频繁"+round+"项集...");
		 Map<String,Integer> Lk_1_tmp=new TreeMap<String,Integer>(); 
	   for(Map.Entry<String, Integer> l:Lk_1.entrySet()){
		   String itemset=l.getKey();
		   String[] item=itemset.split(";");
		   Arrays.sort(item, new StringComparator());
		   String key="";
		   for(String s:item){
			   key=key+s+";";
		   }
		   Lk_1_tmp.put(key, l.getValue());
		   
		 }
	   Lk_1=sortMapByKey(Lk_1_tmp);
	   Map<String,Integer> Ck=apriori_gen(Lk_1);
	   
	   //遍历事务数据库计数
	   for(String t:tlist){
		//   System.out.println(t);
		   Map<String,Integer> Ct=subset(Ck,t);
		   if(Ct!=null){
			   for(Map.Entry<String, Integer> c:Ct.entrySet()){
				   int count=Ck.get(c.getKey()).intValue()+1;
				   Ck.put(c.getKey(), count);
			   }			   
		   }

	   }
	 //  System.out.println("遍历完毕");
	   Lk_1.clear();
	   for(Map.Entry<String, Integer> ct:Ck.entrySet()){
		   if(ct.getValue()>=support){
			   Lk_1.put(ct.getKey(), ct.getValue());
			   L.put(ct.getKey(), ct.getValue());
		   }
	   }
		System.out.println("找到"+Lk_1.size()+"个频繁"+round+"项集。");
	 }
	 System.out.println("挖掘完毕，打印结果。。。");
	 for(Map.Entry<String, Integer> l:L.entrySet()){
		 System.out.println(l.getKey()+": "+l.getValue());
	 }

	}

	
	private static Map<String,Integer> subset(Map<String,Integer> Ck, String t) {
		// TODO Auto-generated method stub
		Map<String,Integer> Ct=new TreeMap<String,Integer>();
		//String[] tsplit=t.split(";");
		boolean flag=true;
		for(String Ck_tmp:Ck.keySet()){
			flag=true;
			String[] Ck_tmp_split=Ck_tmp.split(";");			
			for(String cts:Ck_tmp_split){
				if(!t.contains(cts)){
					flag=false;					
				}				
			}
			if(flag){
				Ct.put(Ck_tmp, 0);
			}
		}
		
		return Ct;
	}


	/**
     * 使用 Map按key进行排序
     * @param map
     * @return 按key排序好的新Map
     */
    public static Map<String,Integer> sortMapByKey(Map<String, Integer> map) {
        if (map == null || map.isEmpty()) {
            return null;
        } 
        Map<String,Integer> sortMap = new TreeMap<String, Integer>(
                new StringComparator()); 
        sortMap.putAll(map); 
        return sortMap;
    }
	/** 
	 * apriori_gen(由频繁K-1项集产生频繁K项候选集)    
	 * @param   事务列表    
	 * @return  频繁1项集  
	 * @Exception 异常对象    
	*/
	public static Map<String,Integer> apriori_gen(Map<String,Integer> Lk_1){
		Map<String,Integer> Ck=new TreeMap<String,Integer>();	
		for(Map.Entry<String, Integer> l1:Lk_1.entrySet()){
			String[] l1_item=l1.getKey().split(";");
			String l1_item_1_k_2=l1.getKey().substring(0,l1.getKey().lastIndexOf(";")-l1_item[l1_item.length-1].length());
/*			if(l1_item.length==1){
				l1_item_1_k_2="";
			}else{
				//l1_item_1_k_2=l1.getKey().substring(0,l1.getKey().lastIndexOf(";"));//1至k-2项	
				l1_item_1_k_2=l1.getKey().substring(0,l1.getKey().lastIndexOf(";"));//1至k-2项
			}*/		
			
			for(Map.Entry<String, Integer> l2:Lk_1.entrySet()){				   
			   String[] l2_item=l2.getKey().split(";");
			   String l2_item_1_k_2=l2.getKey().substring(0,l2.getKey().lastIndexOf(";")-l2_item[l2_item.length-1].length());//1至k-2项		
/*			   if(l2_item.length==1){
				   l2_item_1_k_2="";
			   }else{
				   l2_item_1_k_2=l2.getKey().substring(0,l2.getKey().lastIndexOf(";"));//1至k-2项				   
			   }*/
			   String c="";
			   if((l1_item_1_k_2.equals(l2_item_1_k_2))&&(l1_item[l1_item.length-1].compareTo(l2_item[l2_item.length-1])<0)){
				   c=l1_item_1_k_2+l1_item[l1_item.length-1]+";"+l2_item[l1_item.length-1];//连接，产生候选
				   if(has_infrequent_subset(c,Lk_1)){
					          
					   
					   
					   //剪枝
				   }
				   else{
					   Ck.put(c,0);
				   }
			   }
			   
			}
		}
		
		return Ck;
	}
	
	public static boolean has_infrequent_subset(String c,Map<String,Integer> Lk_1){
		//boolean flag=false;
		String [] t=c.split(";");
		ArrayList<String> c_k=new ArrayList<String>(Arrays.asList(t));
		//c_k.subList(fromIndex, toIndex);
		return false;
		//return flag;
	}
	
	/** 
	 * find_frequent_1_itemsets(find frequent 1 itemsets)    
	 * @param   事务列表    
	 * @return  频繁1项集  
	 * @Exception 异常对象    
	*/
	public static Map<String,Integer> find_frequent_1_itemsets(ArrayList<String> tlist,float support){
		Map<String,Integer> L1=new TreeMap<String,Integer>();		
		for (String t:tlist){
			String itemset[]=t.split(";");
			for(String item:itemset){
				L1.put(item, 0);
			}
		}

		for (String t:tlist){
			String itemset[]=t.split(";");
			for(String item:itemset){
				if(L1.keySet().contains(item)){
				  L1.put(item, L1.get(item).intValue()+1);				  
				}
			}
		}
		Map<String, Integer> L11=new TreeMap<String, Integer>();
		 //遍历频繁1项集	
		 for(Map.Entry<String, Integer> l:L1.entrySet()){
			 if(l.getValue()>=(support*tlist.size())){
				 L11.put(l.getKey(), l.getValue());
	   		     System.out.println(l.getValue()+":"+l.getKey());
	   	  }
		 }
		return L11;
	}
	/** 
	 * getTransactionFromFile(文件中加载事务数据集)    
	 * @param   文件路径    
	 * @return String    事务列表  
	 * @Exception 异常对象    
	*/
	public static ArrayList<String> getTransactionFromFile(String path) throws FileNotFoundException{
		ArrayList<String> tlist=new ArrayList<String>();	
		File f=new File(path);
	    FileReader fr=new FileReader(f);
	    @SuppressWarnings("resource")
		BufferedReader br=new  BufferedReader(fr);
	    String line;
	    try {
			while((line=br.readLine())!=null){
			  tlist.add(line);	
			}
		} catch (IOException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}
	    
	    return tlist;    
	}

}

class StringComparator implements Comparator<String>{
	@Override
	public int compare(String o1, String o2) {
		// TODO Auto-generated method stub
		return o1.compareTo(o2);
	}
}
